Nguyễn Hữu Tuấn trường thành từ lò đào tạo Sông Lam Nghệ An cùng lứa với Phan Văn Đức, Phạm Xuân Mạnh và Bùi Đình Châu. Thành tích ấn tượng nhất của Hữu Tuấn trong màu áo các đội trẻ của Nghệ An là chức vô địch U-17 Quốc gia 2012.[2] Kể từ mùa giải 2015–2018, anh lần lượt đầu quân cho Kon Tum, Đồng Nai và Công An Nhân Dân theo dạng cho mượn.

Không thể chen chân lên đội 1 Sông Lam Nghệ An, Hữu Tuấn đã xin thanh lý hợp đồng đào tạo với đội bóng xứ Nghệ để gia nhập cho Bà Rịa - Vũng Tàu, lúc đó đang thi đấu ở giải hạng Nhì.[3] Sau khi mùa giải 2020 kết thúc, anh không được đội bóng mang biệt danh "chim ó biển" gia hạn hợp đồng và chuyển sang đầu quân cho Phú Thọ.[4]